package 动态规划;

import java.util.ArrayDeque;
import java.util.Deque;

public class 案例0_1背包问题 {

    /**
     * 0-1背包问题,一个物品只能取一次
     * @param weight 物品的重量
     * @param value 物品的价值
     * @param c 背包的容量
     * @return 背包可获得的最大价值
     */
    public int knapsack01(int[] weight,int[] value,int c){
        //递归
        memory=new Integer[c+1][weight.length+1];
        return dg(weight,value,c,weight.length-1);
    }

    Integer[][] memory;
    //方式一:递归方法
    public int dg(int[] weight,int[] value,int c,int index){

        if(index<0||c<=0){
            //下标越出||容量已经不足
            return 0;
        }

        if(memory[c][index]!=null){
            return memory[c][index];
        }

        //情况一:找到最少物品可存入的最大价值;即子序列的最大价值
        int res1 = dg(weight,value,c,index-1);
        int res2=0;
        if(c>=weight[index]){
            //情况二:如果当前背包容量大于当前物品的重量,则选取当前物品,然后递归加上下面的物品
            res2=value[index]+dg(weight,value,c-weight[index],index-1);
        }

        memory[c][index]=Math.max(res1,res2);

        return memory[c][index];
    }

    //方式二:用动态规划求解

    /**
     * [考虑前x个物品][考虑前c容量]
     * 假设 5个物品(重量和价值与序号等价)  容量为20
     * f(0,0)=0;//0个物品,0重量
     * f(0,1)=0;//0个物品,1重量
     * ...
     * f(0,5)=0;//0个物品,5重量
     * f(1,0)=0;//1个物品,0重量
     * f(1,1)=f(0,1)不选当前物品,value[1]+f(1-1,1-weight[1])选当前物品;//max(不选当前物品,选取当前物品后剩余的容量再选取之前的物品)
     * ...
     * f(4,3)=f(3,3)//不选当前物品,value[4]+f(4-1,3-weight[4]);
     */
    public int knapsack02(int[] weight,int[] value,int c){
        //动态规划
        int[][] dp=new int[weight.length+1][c+1];

        for (int i = 0; i < c; i++) {
            dp[0][i]=0;//前0个物品,不管多大容量都是0
        }
        for (int i = 0; i < weight.length; i++) {
            dp[i][0]=0;//前i个物品,容量为0,则价值就为0
        }

        for (int i = 1; i <= weight.length; i++) {
            for (int j = 1; j <= c; j++) {
                /**
                 * 两种情况:
                 * 1.不要当前物品
                 * 2.要当前物品+要了后剩下容量最大价值
                 */
                int res1=dp[i-1][j];//不要当前物品
                int res2=0;
                if(weight[i-1]<=j){
                    //要当前物品,加上剩下容量最大的价值
                    /**
                     * 空间待优化,只需要一维数组即可
                     * 因为[i]只依赖[i-1],不依赖其他元素
                     * 可以让i%2和(i-1)%2即可,还可以继续缩成一行
                     */
                    res2=dp[i-1][j-weight[i-1]]+value[i-1];
                }
                dp[i][j]=Math.max(res1,res2);
            }
        }

        return dp[weight.length][c];
    }

    //动态规划空间优化版
    /**
     * 因为当前行仅仅需要上面一行的两个数据,所以可以将两个合并成一行,变成一维数组
     * 不过记得需要倒序,因为当前节点是需要正上方节点和正上方左边的节点,所以需要倒着来,防止数据覆盖
     */
    public int knapsack03(int[] weight,int[] value,int c){
        //动态规划
        int[] dp=new int[c+1];

        for (int i = 0; i < c; i++) {
            //容量为1~c时填入第[1]个物品得到的价值
            dp[i]=(i>=weight[0]?value[0]:0);
        }

        for (int i = 1; i < weight.length; i++) {
            for (int j = c; j >= weight[i]; j--) {
                dp[j]=Math.max(dp[j],dp[j-weight[i]]+value[i]);
            }
        }
        Deque deque=new ArrayDeque();
        deque.removeFirst();
        return dp[c];
    }

    public static void main(String[] args) {
        案例0_1背包问题 n=new 案例0_1背包问题();
        int[] weight={4,3,1,2,7,6,1,4,3,1,2,7,6,1};
        int[] value= {6,5,3,1,2,4,5,6,7,2,5,6,7,8};
        int result1 = n.knapsack01(weight, value, 23);
        int result2 = n.knapsack02(weight, value, 23);
        int result3 = n.knapsack03(weight, value, 23);
        System.out.println(result1);
        System.out.println(result2);
        System.out.println(result3);
    }

}
